package com.dylan.历史.算法;

import java.util.Arrays;

/**
 * @Auther: ankang
 * @Date: 2019/1/25 14:08
 * @Description:
 */
public class 八皇后问题 {

    public static void main(String[] args) {
        int[] queens = init(8);
        calQueens(queens, 0);
        System.out.println(Arrays.toString(queens));
    }

    private static int[] init(int len) {
        int[] queens = new int[len];
        for (int i = 0; i < len; i++) {
            queens[i] = -1;
        }
        return queens;
    }

    private static boolean calQueens(int[] queens, int row) {
        if (row == queens.length) {
            // 设置完成退出
            return true;
        }
        // 判断当前皇后(row)放置什么位置
        for (int column = 0; column < queens.length; column++) {
            // 判断当前皇后(row)能否设置到column上
            if (isOk(queens, row, column)) {
                // 先将当前皇后(row)放置到column上，如果剩下的皇后不能放置，则下面进行回溯
                queens[row] = column;
                boolean cal = calQueens(queens, row + 1);
                if (cal) {
                    return true;
                } else {
                    // 该位置不能放置皇后，重置该位置
                    queens[row] = -1;
                }
            }
        }
        // 让上一个皇后重新设置位置
        return false;
    }

    private static boolean isOk(int[] queens, int row, int column) {
        int leftUp = column - 1;
        int rightUp = column + 1;
        for (int i = row - 1; i >= 0; i--) {
            // 判断当前列有没有
            if (queens[i] == column) {
                return false;
            }
            // 判断左上角有没有
            if (leftUp >= 0 && queens[i] == leftUp) {
                return false;
            }
            // 判断又上交有没有
            if (rightUp < queens.length && queens[i] == rightUp) {
                return false;
            }
            leftUp--;
            rightUp++;
        }
        return true;
    }
}
